|
In his book ''A New Kind of Science'', Stephen Wolfram described a universal 2-state 5-color Turing machine, and conjectured that a particular 2-state 3-color Turing machine (hereinafter (2,3) Turing machine) might be universal as well. On May 14, 2007, Wolfram announced a $25,000 prize to be won by the first person to prove or disprove the universality of the (2,3) Turing machine.〔(【引用サイトリンク】 url=http://www.wolframscience.com/prizes/tm23/ )〕 On 24 October 2007, it was announced that the prize had been won by Alex Smith, a student in electronics and computing at the University of Birmingham. ==Description== The following table indicates the actions to be performed by the Turing machine depending on whether its current state is A or B, and the symbol currently being read is 0, 1 or 2. The table entries indicate the symbol to be printed, the direction in which the tape head is to move, and the subsequent state of the machine. : The (2,3) Turing machine: *Has no halt state; *Is trivially related to 23 other machines by interchange of states, colors and directions. Minsky (1967) briefly argues that standard (2,2) machines cannot be universal; thus, it might seem that the (2,3) Turing machine would be the smallest possible universal Turing machine (in terms of number of states times number of symbols). However, the results are not directly comparable, because Minsky only considers machines that explicitly halt, which the (2,3) machine does not. More generally, almost all formal definitions of Turing machines differ in details irrelevant to their power, but perhaps relevant to what can be expressed using a given number of states and symbols; there is no single standard formal definition. The (2,3) Turing machine also requires an infinite non-repeating input, again making a direct comparison to earlier small Turing machines problematic. Therefore, though it may be true that the (2,3) machine is in some sense the "smallest possible universal Turing machine", this has not been strictly proven, and the claim is open to debate. location: left The state of the head (up or down droplet (A and B respectively)) and the pattern of color (white, yellow and orange (0,1, and 2 respectively)) in a given row depends solely on the content of the row immediately above it. Even though the machine has a head with only two states, and a tape that can hold only three colors (depending on the initial content of the tape), the machine's output can still be remarkably complex.〔(【引用サイトリンク】 title=Student snags maths prize )〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Wolfram's 2-state 3-symbol Turing machine」の詳細全文を読む スポンサード リンク
|
